package com.sx.sx1.lintcode.day717;

import java.util.ArrayList;
import java.util.List;

public class LC205 {


    static class Interval {
        int start, end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }



    static class Solution {
        /**
         * @param a:       An integer array
         * @param queries: An query list
         * @return: The result list
         */
        public List<Integer> intervalMinNumber(int[] a, List<Interval> queries) {
            SegmentNode root = build(a, 0, a.length - 1); //创建线段树
            List<Integer> ans = new ArrayList<>();
            for (Interval query : queries) {
                ans.add(getmin(root, query.start, query.end));
            }
            return ans;
        }

        public int getmin(SegmentNode root, int start, int end) {
            if (start <= root.start && end >= root.end) return root.minv;
            int m = root.start + (root.end - root.start) / 2;

            int left = Integer.MAX_VALUE;
            int right = Integer.MAX_VALUE;

            if (m >= start) {
                left = getmin(root.left, start, Math.min(m, end));
            }

            if (m < end) {
                right = getmin(root.right, m >= start ? m + 1 : start, end);
            }
            return Math.min(left, right);
        }

        public SegmentNode build(int[] arr, int start, int end) {
            if (start == end) {
                return new SegmentNode(start, end, arr[start]);
            }

            SegmentNode root = new SegmentNode(start, end, Integer.MAX_VALUE);
            int m = start + (end - start) / 2;
            root.left = build(arr, start, m);
            root.right = build(arr, m + 1, end);
            root.minv = Math.min(root.left.minv, root.right.minv);
            return root;
        }


        static class SegmentNode {  //线段树节点定义
            public int start, end, minv; //minv 区间最小值
            public SegmentNode left, right;

            public SegmentNode(int s, int e, int mv) {
                start = s;
                end = e;
                minv = mv;
            }
        }
    }

}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有184条未读消息，请及时查看
205 · 区间最小数
算法
中等
通过率
32%

题目
题解12
笔记
讨论94
排名
记录
描述
给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 [start, end]。 对于每个查询，计算出数组中从下标 start 到 end 之间的数的最小值，并返回在结果列表中。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


在做此题前，建议先完成以下三题：线段树的构造， 线段树的查询，以及线段树的修改。

样例
样例1：
输入：数组 ：[1,2,7,8,5] 查询 ：[(1,2),(0,4),(2,4)]。输出：[2,1,5]
样例2：
输入：数组 ：[4,5,7,1] 查询 ：[(1,2),(1,3)]。输出：[5,1]

挑战
每次查询在O(logN)的时间内完成

标签
相关题目

206
区间求和 I
中等

207
区间求和 II
困难

751
约翰的生意
中等
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
已开启智能提示
发起考试
30 分 00 秒
123456789101112131415161718192021
}
控制台
历史提交

 */




